home *** CD-ROM | disk | FTP | other *** search
/ Almathera Ten Pack 3: CDPD 3 / Almathera Ten on Ten - Disc 3: CDPD3.iso / scope / 201-220 / scopedisk208 / ibem / up100.lzh / Update_techie.doc < prev    next >
Text File  |  1991-03-21  |  4KB  |  70 lines
  1. Techie info, or "How Does it Work?"
  2. -----------------------------------
  3.  
  4. Don't read this unless you actually care how this program works.
  5.  
  6. The method is reminiscent of LZSS encoding.  I don't know exactly what the 
  7. SS stands for, but this isn't LZSS anyway so I'm just going to call it LZF 
  8. (yes, the 'F' stands for Fehdrau; I can't afford vanity plates for my car 
  9. so this will have to do).  Somebody tell me if I'm off-base using L & Z's 
  10. initials in the name.  (Lempel & Ziv, I think their names were.  Apologies
  11. to them if my memory fails me.)
  12.  
  13. There is a control byte for the next 8 elements, which can either be new 
  14. bytes (corresponding bit set to 0) or three-byte references to strings in 
  15. the old program (corresponding bit set to 1).  If a string matches only 
  16. one or two characters in the old file, the individual bytes are stored, 
  17. since that way it is either 9 (control bit + byte) or 18 (2 x (control_bit 
  18. + byte)) bits instead of 25 (control bit plus three byte reference).  
  19. Three or more bytes are stored as a reference, since 25 bits is less 
  20. than 27+ (3+ x (control bit + byte)).
  21.  
  22. The references are to a 4096 byte window into the old file.  They are 
  23. stored as 12 bits (hi->lo) of location and 12 bits (hi->lo) of length.  A 
  24. reference of 4095,4095 is legal, since access outside of the window is 
  25. allowed, so long as it STARTS in the window.  String accesses outside of 
  26. file bounds are not allowed and are cut off if they are found.  
  27.  
  28. The 4096 byte window pointer starts out at the start of the old file.  The 
  29. window itself is bounded by pointer-1024 and pointer+3071.  However, the 
  30. bounds are modified (never the pointer, just the bounds) so that they are 
  31. never outside of the file bounds, except with files smaller than 4096 bytes 
  32. in which the upper bound is out of the file.  The pointer increments by a 
  33. value equal to the length of the longest match if it is between 1 and 32 
  34. bytes.  Matches longer than 32 bytes (arbitrary limit, seems to work best)
  35. move the pointer to the end of that match in the old file.  Using this 
  36. method the dearchiving process can also figure out which 4096 bytes of the 
  37. old file are in the window.
  38.  
  39. "Seems kinda slow."  Yeah.  Unlike LZSS and LZH, I can't use a binary 
  40. search tree to find the longest match because then I'd have to rebuild the
  41. tree after every change in the window position.  Instead, I had to 
  42. literally search the entire damn buffer.  I got a little clever about it,
  43. though, so that if it, say, had a five-byte match already, it wouldn't
  44. check the first five bytes of any subsequent string unless the sixth byte
  45. matched the given string.  That's the best I could think of.  Better
  46. ideas, anyone?  Anyway, using that method it's only slow on different
  47. files.  A perfect match is really very fast, and close matches are quite
  48. respectable.  If it goes too slow, the .up file is probably not going to 
  49. be very small anyway.
  50.  
  51. How well does it work?  Quite, usually, for me.  It's really meant as a 
  52. patch program, not a full upgrade deal.  The problem with executables is 
  53. that 9/10 branches are relative, and therefore are changed if anything is
  54. added or deleted between the branch and its destination, so the relative 
  55. offset changes and causes a string break.  Similarly, if your compiler
  56. uses a register to access a global data area (ie. Manx's use of A4), and 
  57. you add one single variable at the start of the data area, every 
  58. reference to a global variable will be different.  Too much of that and 
  59. Update's not going to find many long strings.  It's good for, and meant 
  60. for, fixing that nasty division by zero error, unallocated string, 
  61. version number, etc, but not changing 500 instances of printf() to 
  62. fprintf(stderr,).  Get it?
  63.  
  64. By the way, if nothing ever matches, the resultant .up file will be 12.5% 
  65. larger than the original (9 bits per new byte).
  66.  
  67. For the future:  Maybe add Huffman to the code.  The control bytes, new
  68. bytes, and buffer locations should be more or less random.  However, 
  69. lengths will likely cluster.  But that's another story.
  70.